package Knapsack;

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;
import javax.swing.JOptionPane;

/**
 *
 * @author Keith & Jonas
 */
public class Knapsack {

    private ArrayList<KnapsackElement> allElements = new ArrayList<KnapsackElement>();
    private ArrayList<KnapsackElement> solution = new ArrayList<KnapsackElement>();
    private ArrayList<KnapsackElement> temp = new ArrayList<KnapsackElement>();
    private int maxValue = 0;
    private int capacity;
    private int nCombinations = 0; // Used to keep track of how many combinations we have tried
    private String[] files = {"knapsack.txt", "knapsack2.txt", "knapsack3.txt"};

    /**
     *
     * @param filename
     */
    public Knapsack() throws FileNotFoundException, IOException {
        readFile();
//        printElements(getCombination());
//        System.out.println("Maximum Total Value: " + maxValue);
//        System.out.println("Max Size: " + sumSize(solution));
//        System.out.println(nCombinations);
        int total = ver2(allElements);
        System.out.println("Total value in knapsack: " + total);
        printElements(solution);
    }

    /**
     *
     * @return
     */
    public ArrayList<KnapsackElement> getCombination() {
        calculateSolution(allElements, 0);
        return solution;
    }

    /**
     *
     * @param elements
     * @return The total value of the elements in the list
     */
    private int sumValue(ArrayList<KnapsackElement> elements) {
        int sum = 0;
        for (KnapsackElement ke : elements) {
            sum += ke.getValue();
        }
        return sum;
    }

    /**
     *
     * @param elements
     * @return The total size of the elements in the list
     */
    private int sumSize(ArrayList<KnapsackElement> elements) {
        int sum = 0;
        for (KnapsackElement ke : elements) {
            sum += ke.getSize();
        }
        return sum;
    }

    /**
     *
     * @throws FileNotFoundException
     * @throws IOException
     */
    public void readFile() throws FileNotFoundException, IOException {
        String ans = JOptionPane.showInputDialog("Choose which test case to run: (\"1\", \"2\" or \"3\")\nIf none of these are chosen test case number one is run");
        String file = "";
        if (ans.equals("1")) {
            file = files[0];
        } else if (ans.equals("2")) {
            file = files[1];
        } else if (ans.equals("3")) {
            file = files[2];
        } else {
            file = files[0];
        }
        Scanner sc = new Scanner(new FileReader(file));
        String t = "";
        while (sc.hasNext()) {
            t = sc.next();
            if (!(t.contains("capacity"))) {
                allElements.add(parseText(t));
            } else {
                capacity = Integer.parseInt("" + t.substring(t.indexOf("=") + 1));
            }
        }
    }

    /**
     *
     * @param s
     * @return
     */
    public KnapsackElement parseText(String s) {
        String value = "", size = "";
        int i = 1;
        while (s.charAt(i) != ',') {
            size += s.charAt(i);
            i++;
        }
        i++;
        while (s.charAt(i) != ')') {
            value += s.charAt(i);
            i++;
        }
        return new KnapsackElement(Integer.parseInt(size), Integer.parseInt(value));
    }

    /**
     *
     * @param elements
     */
    public void printElements(ArrayList<KnapsackElement> elements) {
        System.out.println("------ Combination -------");
        for (KnapsackElement ke : elements) {
            ke.printElement();
        }
        System.out.println("--------------------------");
    }

    /**
     *
     * @param e The list of element to try to fit into the knapsack
     * @param i An index to keep track on how to divide the list into subset
     */
    public void calculateSolution(ArrayList<KnapsackElement> e, int i) {
        nCombinations++;
        if (sumSize(e) <= capacity) { // does the list fit into the knapsack
            int sum = 0;
            if ((sum = sumValue(e)) > maxValue) { // is the total value of the list the largest so far
                solution = e;
                maxValue = sum;
            }
        } else { // if we find a subset that fits in the knapsack we don't try the subsets of that list
            for (int k = i; k < e.size(); k++) { // traverse the list and recursively try the subsets
                temp = (ArrayList<KnapsackElement>) e.clone();
                temp.remove(k);
                calculateSolution(temp, k);
            }
        }
    }

    public int ver2(ArrayList<KnapsackElement> e) {
        int n = e.size();
        System.out.println("N = " + n + " CAP = " + capacity);
        int[][] MAGIC = new int[n + 1][capacity + 1];
//        for (int i = 0; i <= capacity; i++) {
//            MAGIC[0][i] = 0;
//        }

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (e.get(i - 1).getSize() > w) {
                    MAGIC[i][w] = MAGIC[i - 1][w];
                } else {
                    MAGIC[i][w] = Math.max(MAGIC[i - 1][w], e.get(i - 1).getValue() + MAGIC[i - 1][w - e.get(i - 1).getSize()]);
                }
            }
        }

        solution.clear();

        int K = capacity;
        for (int i = n; i >= 1; i--) {
            if (MAGIC[i][K] != MAGIC[i - 1][K]) {
                solution.add(e.get(i - 1));
                K -= e.get(i - 1).getSize();
            }
        }
//        String s = "";
//        for (int i = 0; i < n + 1; i++) {
//            s += i + "|";
//            for (int j = 0; j < capacity + 1; j++) {
//                s += " " + MAGIC[i][j];
//            }
//            s += "\n";
//        }
//        System.out.print(s);
        return MAGIC[n][capacity];
    }
}
